// https://leetcode.cn/problems/letter-case-permutation/description/

// 算法思路总结：
// 1. 回溯算法生成字母大小写的全排列
// 2. 遇到字母时分别尝试小写和大写两种选择
// 3. 遇到数字时直接保留原字符
// 4. 遍历到字符串末尾时保存当前排列
// 5. 时间复杂度：O(2^k × n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <cstring>
#include <vector>
#include <algorithm>

class Solution 
{
    vector<string> ret;
    string path;
public:
    vector<string> letterCasePermutation(string s) 
    {
        ret.clear();

        dfs(s, 0);
        return ret;
    }

    void dfs(string& s, int pos)
    {
        if (pos == s.size())
        {
            ret.push_back(path);
            return ;
        }

        if (isalpha(s[pos]))
        {
            path.push_back(tolower(s[pos]));
            dfs(s, pos + 1);
            path.pop_back();

            path.push_back(toupper(s[pos]));
            dfs(s, pos + 1);
            path.pop_back();
        }
        else
        {
            path.push_back(s[pos]);
            dfs(s, pos + 1);
            path.pop_back();
        }
    }
};

int main()
{
    string s1 = "a1b2", s2 = "3z4";
    Solution sol;

    auto vs1 = sol.letterCasePermutation(s1);
    auto vs2 = sol.letterCasePermutation(s2);
    
    for (const string& str : vs1)
        cout << str << " ";
    cout << endl;

    for (const string& str : vs2)
        cout << str << " ";
    cout << endl;

    return 0;
}